package com.hy.backtracking2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class SumOfCombine3 {


    /**
     * 40.组合总和II
     * 力扣题目链接
     *
     * 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
     *
     * candidates 中的每个数字在每个组合中只能使用一次。
     *
     * 说明： 所有数字（包括目标数）都是正整数。 解集不能包含重复的组合。
     *
     * 示例 1: 输入: candidates = [10,1,2,7,6,1,5], target = 8, 所求解集为: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]
     *
     * 示例 2: 输入: candidates = [2,5,2,1,2], target = 5, 所求解集为: [   [1,2,2],   [5] ]
     *
     * 思路
     * 如果对回溯算法基础还不了解的话，我还特意录制了一期视频：带你学透回溯算法（理论篇） 可以结合题解和视频一起看，希望对大家理解回溯算法有所帮助。
     *
     * 这道题目和39.组合总和如下区别：
     *
     * 本题candidates 中的每个数字在每个组合中只能使用一次。
     * 本题数组candidates的元素是有重复的，而39.组合总和是无重复元素的数组candidates
     * 最后本题和39.组合总和要求一样，解集不能包含重复的组合。
     *
     * 本题的难点在于区别2中：集合（数组candidates）有重复元素，但还不能有重复的组合。
     *
     */
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    int sum = 0;
    public List<List<Integer>> combineSum(int [] candidates,int target,int idx){

        //为了将重复的数字都放到一起，所以先进行排序
        Arrays.sort(candidates);
        combine(res,path,candidates,target,idx);
        return res;
    }

    public void combine(List<List<Integer>> res, LinkedList<Integer> path, int [] candidates, int target,int idx){
        if (sum == target){
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = idx; i <candidates.length && sum + candidates[i] <= target; i++) {
            //正确剔除重复解的办法
            //跳过同一树层使用过的元素
            if (i > idx && candidates[i] == candidates[i - 1] ){
                continue;
            }

            sum += candidates[i];
            path.add(candidates[i]);
            combine(res,path,candidates,target,i+1);
            // 回溯
            int temp = path.getLast();
            sum -= temp;
            path.removeLast();
        }
    }

    public static void main(String[] args) {
        int [] candidates ={10,1,2,7,6,1,5};
        SumOfCombine3 sumOfCombine = new SumOfCombine3();
        System.out.println("res: "+ sumOfCombine.combineSum(candidates, 8, 0));

    }
}
